package com.yoshino.leetcode.improve40.twelveth;

import java.util.Stack;

class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for (String token : tokens) {
            if (token.length() == 1 && !Character.isDigit(token.charAt(0))) {
                // 符号
                Integer second = stack.pop();
                Integer first = stack.pop();
                switch (token.charAt(0)) {
                    case '+':
                        first += second;
                        break;
                    case '-':
                        first -= second;
                        break;
                    case '*':
                        first *= second;
                        break;
                    case '/':
                        first /= second;
                        break;
                }
                stack.push(first);
            } else {
                stack.push(Integer.parseInt(token));
            }
        }
        return stack.pop();
    }

    public int[] asteroidCollision(int[] asteroids) {
        Stack<Integer> stack = new Stack<>();
        for (int asteroid : asteroids) {
            boolean isLive = true;
            while (isLive && asteroid < 0 && !stack.isEmpty() && stack.peek() > 0) {
                isLive = stack.peek() < -asteroid;
                if (stack.peek() <= -asteroid) {
                    stack.pop();
                }
            }
            if (isLive) {
                stack.push(asteroid);
            }
        }
        return stack.stream().mapToInt(Integer::intValue).toArray();
    }

    public int[] dailyTemperatures(int[] temperatures) {
        // 单调栈
        int[] res = new int[temperatures.length];
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < temperatures.length; i++) {
            if (stack.isEmpty() || temperatures[stack.peek()] >= temperatures[i]) {
                stack.push(i);
            } else {
                // 栈顶 小于 当前元素
                int cur = stack.pop();
                res[cur] = i - cur;
                while (!stack.isEmpty() && temperatures[stack.peek()] < temperatures[i]) {
                    cur = stack.pop();
                    res[cur] = i - cur;
                }
                stack.push(i);
            }
        }
        return res;
    }
}